#include "directed_graph.h"



//! 
    //! 将节点添加到小型或大型整数对应的 “map” 中
    /*!
     * \param node                   要添加的节点  
     * \param cpt                    节点计数器，引用传递以便修改 
     * \param correspondance         存储节点编号的向量
     * \param corres                 存储节点映射的向量 
     * \param corres_big_ids         存储大节点编号映射的映射 
     * \param renumbering            是否进行重编号的标志
     */
static void add_to_map(unsigned int node,                                  
                       unsigned int& cpt,                                
                       vector<unsigned long>& correspondance,              
                       vector<int>& corres,                                 
                       map<unsigned long, unsigned int>& corres_big_ids,   
                       bool renumbering)                                   
{
    if (renumbering)    // 如果需要重编号  
    {
        if (node < MAP_LIMIT)   // 如果节点编号小于MAP_LIMIT 
        {
            if (corres[node] == -1) // 如果corres向量中对应节点的值为-1（表示尚未映射）
            {
                corres[node] = cpt++;   // 将节点编号映射为新的计数器值，并递增计数器  
                correspondance.push_back(node); // 将节点编号添加到correspondance向量中 
            }
        }
        else    // 如果节点编号大于或等于MAP_LIMIT  
        {
            if (corres_big_ids.find(node) == corres_big_ids.end()) // 如果corres_big_ids映射中不存在该节点编号 
            {
                corres_big_ids[node] = cpt++;                   // 将节点编号映射为新的计数器值，并递增计数器
                correspondance.push_back(node);                 // 将节点编号添加到correspondance向量中  
            }
        }
    }
    else if (cpt < node) // 如果不进行重编号，并且当前计数器的值小于节点编号  
    {
        cpt = node;     // 更新计数器的值为节点编号（确保计数器至少与最大的节点编号一样大） 
    }
}


    //! 获取一个给定节点node在重编号后的映射值
    /*!
     * \param node              要获取映射的节点编号
     * \param corres            存储小于MAP_LIMIT的节点的映射关系的向量
     * \param corres_big_ids    存储大于或等于MAP_LIMIT的节点的映射关系的映射 
     * \param renumbering       是否进行了重编号的标志
     */
static unsigned int get_mapped_node(unsigned long int node,                                 
                                    const vector<int>& corres,                               
                                    const map< unsigned long, unsigned int>& corres_big_ids, 
                                    bool renumbering)                                        
{
    unsigned int mapped_node = node;                // 初始化映射后的节点编号为原始节点编号
    if (renumbering)                                // 如果进行了重编号
    {
        if (node < MAP_LIMIT)
        {
            mapped_node = corres[node];             // 从corres向量中获取映射后的节点编号
        }
        else                                        // 如果节点编号大于或等于MAP_LIMIT  
        {
            mapped_node = corres_big_ids.at(node);  // 从corres_big_ids映射中获取映射后的节点编号
        }
    }
    return mapped_node;
}

// 为输入图构建新的编号映射，并返回cpt（节点的数量）
// 如果reproducibility = true，重编号后的图将以边列表格式写入文件：src dest (weight)
static unsigned int build_map(Directed_Graph& g,
                              string filename,
                              vector<unsigned long>& correspondance,
                              vector<vector<pair<unsigned int, double>>>& LOUT,
                              vector<vector<pair<unsigned int, double>>>& LIN,
                              bool renumbering, bool reproducibility, bool verbose)
{
    vector<int> corres(MAP_LIMIT, -1);
    map<unsigned long, unsigned int> corres_big_ids;
    if (renumbering && verbose)
    {
        cerr << "renumbering graph..." << endl;
    }
    ofstream foutput;
    if (reproducibility)
    {
        size_t name_size = filename.size();
        string name = filename.substr(0, name_size - 4);
        string extension = filename.substr(name_size - 4, name_size);
        string tmp = name + "_renum";
        tmp += extension;
        foutput.open(tmp, fstream::out | fstream::binary);
    }

    ifstream finput;
    finput.open(filename, fstream::in);
    assert(finput.rdstate() == ios::goodbit);

    unsigned int cpt = 0;

    // 读取邻接链表文件提取节点和边
    string line;
    unsigned int src = 0;
    unsigned int dest = 0;
    while (getline(finput, line))
    {
        size_t number_of_tokens = 0;

        char* line_to_split = new char[line.size() + 1];
        strcpy(line_to_split, line.c_str());

        char* token = strtok(line_to_split, " \t");

        while (token != NULL && number_of_tokens < 2)
        {
            if (number_of_tokens == 0)
                src = atoi(token);
            if (number_of_tokens == 1)
                dest = atoi(token);
            number_of_tokens++;
            token = strtok(NULL, " ");
        }

        assert(number_of_tokens == 2);

        delete[] line_to_split;

        add_to_map(src, cpt, correspondance, corres, corres_big_ids, renumbering);
        add_to_map(dest, cpt, correspondance, corres, corres_big_ids, renumbering);
    }


    // 判断节点是否从零开始编号
    if (!renumbering)
    {
        // renumbering = false，节点编号从零开始，所以节点数量是cpt+1
        ++cpt;
        for (unsigned int i = 0; i < cpt; ++i)
        {
            correspondance.push_back(i);    // 将从0到cpt-1的整数依次添加到correspondance向量中
        }
    }

    LOUT.resize(cpt);
    LIN.resize(cpt);

    finput.clear();
    finput.seekg(0);    // 将文件输入流 finput 的读取位置（或称为“get”位置）设置为文件的开始。0 是偏移量，表示从文件的开头开始计算。


    while (getline(finput, line))
    {
        unsigned int map_src, map_dest;
        double weight = 1.f;
        size_t number_of_tokens = 0;

        char* line_to_split = new char[line.size() + 1];
        strcpy(line_to_split, line.c_str());

        char* token = strtok(line_to_split, " \t");

        while (token != NULL && number_of_tokens < 2)
        {
            if (number_of_tokens == 0)
            {
                src = atoi(token);
            }
            if (number_of_tokens == 1)
            {
                dest = atoi(token);
            }
            number_of_tokens++;
            token = strtok(NULL, " ");
        }

        if (token != NULL)//无论weight是否等于true，只要token读取到权重就将weight设置为true，并保存权重
        {
            if (!g.is_weighted())
            {
                g.set_weighted(true);
            }
            weight = atof(token);
        }

        delete[] line_to_split;

        map_src = get_mapped_node(src, corres, corres_big_ids, renumbering);
        map_dest = get_mapped_node(dest, corres, corres_big_ids, renumbering);

        LOUT[map_src].push_back(make_pair(map_dest, weight));
        LIN[map_dest].push_back(make_pair(map_src, weight));

        if (reproducibility)
        {
            foutput << map_src << " " << map_dest;
            if (g.is_weighted())
            {
                foutput << " " << weight;
            }
            foutput << endl;
        }
    }

    if (reproducibility)
    {
        foutput.close();
    }
    return cpt;
}

// 根据出度邻接列表LOUT和入度邻接列表LIN初始化图对象g的所有属性。
void init_attributes(Directed_Graph& g, 
                     vector<vector<pair<unsigned int, double>>>& LOUT, 
                     vector<vector<pair<unsigned int, double>>>& LIN, 
                     bool verbose)
{
    if (verbose)
    {
        cerr << "initializing graph..." << endl;
        cerr << "number of nodes: " << g.nodes << endl;
    }

    // 创建出度序列
    g.outdegrees.resize(g.nodes);
    unsigned long int tot = 0;
    for (size_t i = 0; i < g.nodes; ++i)
    {
        tot += (unsigned long int) LOUT[i].size();
        g.outdegrees[i] = tot;
    }
    g.arcs = g.outdegrees[g.nodes - 1];
    g.outcoming_arcs.resize(g.arcs);

    if (g.weighted)
    {
        g.outcoming_weights.resize(g.arcs);
    }
    else
    {
        g.outcoming_weights.resize(0);
    }

    // 存储出度和权重
    unsigned long int total_LOUT = 0;
    for (size_t i = 0; i < g.nodes; ++i)
    {
        for (auto edge : LOUT[i])
        {
            g.outcoming_arcs[total_LOUT] = edge.first;
            if (g.weighted)
            {
                g.outcoming_weights[total_LOUT] = edge.second;
            }
            ++total_LOUT;
        }
    }

    // 释放内存
    for (size_t i = 0; i < LOUT.size(); ++i)
    {
        LOUT[i].clear();
        vector<pair< unsigned int, double>>().swap(LOUT[i]);
    }

    LOUT.clear();
    vector<vector<pair< unsigned int, double>>>().swap(LOUT);

    // 创建入度序列
    g.indegrees.resize(g.nodes);
    tot = 0;
    for (size_t i = 0; i < g.nodes; ++i)
    {
        tot += (unsigned long int) LIN[i].size();
        g.indegrees[i] = tot;
    }
    g.incoming_arcs.resize(g.arcs);

    if (g.weighted)
    {
        g.incoming_weights.resize(g.arcs);
    }
    else
    {
        g.incoming_weights.resize(0);
    } 

    // 存储入度和权重
    unsigned long int total_LIN = 0;
    for (size_t i = 0; i < g.nodes; ++i)
    {
        for (auto edge : LIN[i])
        {
            g.incoming_arcs[total_LIN] = edge.first;
            if (g.weighted)
            {
                g.incoming_weights[total_LIN] = edge.second;
            }
            ++total_LIN;
        }
    }

    // 释放内存
    for (size_t i = 0; i < LIN.size(); ++i)
    {
        LIN[i].clear();
        vector<pair<unsigned int, double>>().swap(LIN[i]);
    }

    LIN.clear();
    vector<vector<pair<unsigned int, double>>>().swap(LIN);

    if (verbose)
    {
        cerr << "number of arcs: " << g.arcs << endl;
    }

    // 计算整个图的权重
    g.total_weight = 0.;

    for (unsigned int i = 0; i < g.nodes; ++i)
    {
        g.total_weight += g.weighted_out_degree(i);
    }

    if (verbose)
    {
        cerr << "total weight: " << g.total_weight << endl << "done." << endl;
    }
}


//
//Directed_Graph定义
//
Directed_Graph::Directed_Graph()
{
    this->nodes = 0;
    this->arcs = 0;
    this->total_weight = 0;
    this->weighted = false;

    this->outcoming_arcs.resize(0);
    this->incoming_arcs.resize(0);
    this->outcoming_weights.resize(0);
    this->alpha_out.resize(0);

    this->incoming_weights.resize(0);
    this->outdegrees.resize(0);
    this->indegrees.resize(0);
    this->alpha_in.resize(0);
}

Directed_Graph::Directed_Graph(string filename, 
                               bool reproducibility, 
                               bool renumbering, 
                               bool verbose)
{
    vector<vector<pair<unsigned int, double>>> LOUT;
    vector<vector<pair<unsigned int, double>>> LIN;

    string extension = filename.substr(filename.size() - 4, filename.size());   //获取文件后缀名（eg: .txt）

    this->weighted = true;
    if (extension != ".bin") 
    {
        this->correspondance.resize(0);
        this->nodes = build_map(*this, 
                                filename, this->correspondance, 
                                LOUT, LIN, renumbering, reproducibility, verbose);

        init_attributes(*this, LOUT, LIN, verbose);
        string name = filename.substr(0, filename.size() - 4);
        //this->write(name + ".bin");
    }
    else
    {
        this->load(filename, verbose);
    } 
}

Directed_Graph::Directed_Graph(vector<vector<pair<unsigned int, double>>> adjacency_list, 
                               bool reproducibility, 
                               bool renumbering, 
                               bool verbose)
{
    this->weighted = true;
    vector<vector<pair<unsigned int, double>>> LIN(adjacency_list.size());
    LIN.resize(adjacency_list.size());
    this->correspondance.resize(0);
    for (unsigned int i = 0; i < adjacency_list.size(); i++)
    {
        correspondance.push_back(i);
    }
        
    this->nodes = adjacency_list.size();

    // 遍历邻接链表，从而创建节点的入度, 邻接链表直接作为节点的出度   */
    for (unsigned int i = 0; i < adjacency_list.size(); i++) 
    {
        for (auto v : adjacency_list[i]) 
        {
            LIN[v.first].push_back(make_pair(i, v.second));
        }
    }

    init_attributes(*this, adjacency_list, LIN, verbose);
}

Directed_Graph::Directed_Graph(vector<vector<unsigned int>> adjacency_list, 
                               bool reproducibility, 
                               bool renumbering, 
                               bool verbose, bool weighted)
{
    this->weighted = false;
    vector<vector<pair<unsigned int, double>>> LOUT(adjacency_list.size());
    vector<vector<pair<unsigned int, double>>> LIN(adjacency_list.size());
    LOUT.resize(adjacency_list.size());
    LIN.resize(adjacency_list.size());
    this->correspondance.resize(0);
    for (unsigned int i = 0; i < adjacency_list.size(); i++)
    {
        correspondance.push_back(i);
    }
        
    this->nodes = adjacency_list.size();

    /* 遍历邻接链表，从而创建节点的出度和入度 */
    for (unsigned int i = 0; i < adjacency_list.size(); i++) 
    {
        for (auto v : adjacency_list[i]) 
        {
            LOUT[i].push_back(make_pair(v, 1));
            LIN[v].push_back(make_pair(i, 1));
        }
    }

    init_attributes(*this, LOUT, LIN, verbose);
}

Directed_Graph::Directed_Graph(const Directed_Graph& g)
{
    this->weighted          = g.weighted;
    this->nodes             = g.nodes;
    this->arcs              = g.arcs;
    this->total_weight      = g.total_weight;

    this->outcoming_arcs    = g.outcoming_arcs;
    this->incoming_arcs     = g.incoming_arcs;
    this->outdegrees        = g.outdegrees;
    this->alpha_out         = g.alpha_out;

    this->indegrees         = g.indegrees;
    this->outcoming_weights = g.outcoming_weights;
    this->incoming_weights  = g.incoming_weights;
    this->alpha_in          = g.alpha_in;

    this->correspondance    = g.correspondance;
}

void Directed_Graph::write(string outfile)
{
    ofstream foutput;
    foutput.open(outfile, fstream::out | fstream::binary);
    assert(foutput.rdstate() == ios::goodbit);

    // 将图的所有属性写入二进制文件
    foutput.write((char*)(&this->nodes), sizeof(unsigned int));
    foutput.write((char*)(&this->outdegrees[0]), sizeof(unsigned long) * this->nodes);
    foutput.write((char*)(&this->outcoming_arcs[0]), sizeof(unsigned int) * this->arcs);
    if (this->weighted)
    {
        foutput.write((char*)(&this->outcoming_weights[0]), sizeof(double) * this->arcs);
    }
    foutput.write((char*)(&this->indegrees[0]), sizeof(unsigned long) * this->nodes);
    foutput.write((char*)(&this->incoming_arcs[0]), sizeof(unsigned int) * this->arcs);
    if (this->weighted)
    {
        foutput.write((char*)(&this->incoming_weights[0]), sizeof(double) * this->arcs);
    }        
    foutput.write((char*)(&this->correspondance[0]), sizeof(unsigned long) * this->nodes);
    foutput.close();
}

void Directed_Graph::load(string filename, bool verbose)
{
    /* 读取二进制文件 */
    ifstream finput;
    finput.open(filename, fstream::in | fstream::binary);
    assert(finput.rdstate() == ios::goodbit);
    this->outcoming_weights.resize(0);
    this->incoming_weights.resize(0);

    finput.read((char*)&this->nodes, sizeof(unsigned int));
    if (verbose)
    {
        cerr << "number of nodes: " << this->nodes << endl;
    }

    this->outdegrees.resize(this->nodes);
    finput.read((char*)&this->outdegrees[0], this->nodes * sizeof(unsigned long));

    this->arcs = outdegrees[this->nodes - 1];
    this->outcoming_arcs.resize(this->arcs);
    finput.read((char*)(&this->outcoming_arcs[0]), this->arcs * sizeof(unsigned int));

    if (this->weighted) 
    {
        this->outcoming_weights.resize(arcs);
        finput.read((char*)&this->outcoming_weights[0], this->arcs * sizeof(double));
    }

    this->indegrees.resize(this->nodes);
    finput.read((char*)&this->indegrees[0], this->nodes * sizeof(unsigned long));

    if (verbose)
    {
        cerr << "number of arcs:" << this->indegrees[this->nodes - 1] << endl;
    }
        
    this->incoming_arcs.resize(this->arcs);
    finput.read((char*)(&this->incoming_arcs[0]), this->arcs * sizeof(unsigned int));

    if (this->weighted) 
    {
        this->incoming_weights.resize(this->arcs);
        finput.read((char*)&this->incoming_weights[0], this->arcs * sizeof(double));
    }

    this->correspondance.resize(this->nodes);
    finput.read((char*)(&this->correspondance[0]), this->nodes * sizeof(unsigned long));

    this->total_weight = 0.f;
    for (unsigned int i = 0; i < this->nodes; i++) 
    {
        this->total_weight += this->weighted_out_degree(i);
    }

    if (verbose)
    {
        cerr << "total weight: " << this->total_weight << endl;
    }
        
    finput.close();
}

void Directed_Graph::display() const
{
    for (unsigned int node = 0; node < this->nodes; ++node) 
    {
        size_t p = this->out_neighbors(node);
        cout << this->correspondance[node] << ":";
        for (unsigned int i = 0; i < out_degree(node); i++) 
        {
            if (this->weighted)
            {
                cout << " (" << this->outcoming_arcs[p + i] << " " << this->outcoming_weights[p + i] << ")";
            }
            else
            {
                cout << " " << this->outcoming_arcs[p + i];
            }               
        }
        cout << endl;
    }
}

double Directed_Graph::count_selfloops(unsigned int node)
{
    assert(node < this->nodes);
    size_t p = this->out_neighbors(node);
    for (unsigned int i = 0; i < this->out_degree(node); i++) 
    {
        if (this->outcoming_arcs[p + i] == node) 
        {
            if (this->weighted)
            {
                return this->outcoming_weights[p + i];
            }     
            else
            {
                return 1.;
            }    
        }
    }
    return 0.;
}

double Directed_Graph::weighted_out_degree(unsigned int node)
{
    assert(node < this->nodes);
    if (!this->weighted)
    {
        return this->out_degree(node);
    }  
    else 
    {
        size_t p = this->out_neighbors(node);
        double res = 0;
        for (unsigned int i = 0; i < this->out_degree(node); i++)
        {
            res += this->outcoming_weights[p + i];
        }   
        return res;
    }
}

double Directed_Graph::weighted_in_degree(unsigned int node)
{
    assert(node < this->nodes);
    if (!this->weighted)
    {
        return this->in_degree(node);
    }       
    else 
    {
        size_t p   = this->in_neighbors(node);
        double res = 0;
        for (unsigned int i = 0; i < this->in_degree(node); i++)
        {
            res += this->incoming_weights[p + i];
        }     
        return res;
    }
}



double Directed_Graph::get_edge_weight(unsigned int node1, unsigned int node2)
{
    assert(node1 < this->nodes && node2 < this->nodes);
    if (!this->weighted)
    {
        // cerr << " An unweighted graph, where all weights are 1.0.\n ";
        return 1;
    }
    else
    {
        size_t p = this->out_neighbors(node1);
        double weight = 0;
        for (unsigned int i = 0; i < this->out_degree(node1); i++)
        {
            if (this->outcoming_arcs[p + i] == node2)
            {
                return this->outcoming_weights[p + i];
            }
        }
        // cerr << " No edge!!\n ";
        return 0;
    }
}





//Directed_Graph Directed_Graph::disparity_filter(void)
//{
//    Directed_Graph temp_graph;       
//    for (auto node = 0; node < this->nodes; node++)
//    {
//        int k_out = this->out_degree(node);
//        int k_in  = this->in_degree(node);
//
//        if (k_out > 1)                      // 如果节点不止与一个节点相连
//        {
//            size_t p = this->out_neighbors(node);
//            double sum_w_out = this->weighted_out_degree(node);
//            for (unsigned int i = 0; i < k_out; i++)
//            {
//                double w            = this->outcoming_weights[p + i];
//                double p_ij_out     = w / sum_w_out;
//                double alpha_ij_out = 1 - (k_out - 1) *         // 计算alpha的值
//                    simpsons_quad([k_out](double x)->double {return pow(1 - x, k_out - 2); },
//                        0,
//                        p_ij_out,       // 辛普森积分
//                        1e-2);
//                this->alpha_out.push_back(alpha_ij_out);
//            }
//        }
//        else if (k_out == 1)
//        {
//            this->alpha_out.push_back(0);
//        }
//        if (k_in > 1)
//        {
//            size_t p = this->in_neighbors(node);
//            double sum_w_in = this->weighted_in_degree(node);
//            for (unsigned int j = 0; j < k_in; j++)
//            {
//                double w            = this->incoming_weights[p + j];
//                double p_ij_in      = w / sum_w_in;
//                double alpha_ij_in  = 1 - (k_in - 1) *
//                    simpsons_quad([k_in](double x)->double {return pow(1 - x, k_in - 2); },
//                        0,
//                        p_ij_in,
//                        1e-5);
//                this->alpha_in.push_back(alpha_ij_in);
//            }
//        }
//    }
//    temp_graph = *this;         // 拷贝当前的graph，避免直接修改原graph
//    double Q1_out = get_quantile_Q1(temp_graph.alpha_out);
//
//    return temp_graph;
//}